Non-patent literature 1 describes a three-party secure function computation which is a technique for performing a computation including multiplication and addition while concealing data and ensuring validity of the result of the computation. This is a protocol that derives the result of an arithmetic/logical operation by cooperative computations by three parties (three computing entities) without reconstructing distributed input values. In the three-party secure function computation protocol, a secure product-sum combination system treats data as natural numbers less than a predetermined prime p. To conceal data, the data, a, is divided into three and distributed so that the following condition is satisfied.a=a0+a1+a2 mod p 
In practice, the secure product-sum combination system generates random numbers a1 and a2 so that a0=a−a1−a2. Then, (a0, a1), (a1, a2) and (a2, a0) are sent to three parties, X, Y and Z, respectively. Since a1 and a2 are random numbers, none of the parties X, Y and Z has information about a, but if any two of the parties cooperate, a can be reconstructed.
The concealment is commutative because the concealment is additive sharing. Accordingly, adding the shared values together and then reconstructing the values yields the same result as reconstructing the values and then adding the values together. That is, addition and multiplication by a constant can be performed in a distributed manner without communication. Multiplication is also possible, although communication and generation of random numbers are required. Accordingly, a logic circuit can be configured so that any computations can be performed. An example of the three-party secure function computation will be described below. While a computation result in the three-party secure function computation protocol is the remainder of division by p, “mod p” will be omitted in the following description for the sake of simplicity.
(1) Reconstruction of Secret Data a Distributed Among X, Y and Z
X sends a0 to Y and a1 to Z. Y sends ai to Z and a2 to X. Z sends a2 to X and a0 to Y.
X computes a0+a1+a2 to reconstruct a if a2 received from Y and a2 received from Z are equal. Y computes a0+a1+a2 to reconstruct a if a0 received from X and a0 received from Z are equal. Z computes a0+ai+a2 to reconstruct a if a1 received from X and ai received from Y are equal.
(2) Secure Computation of C=a+b
Assume that data b is also concealed by distribution among X, Y and Z in the same way as data a, namely (b0, b1), (b1, b2) and (b2, b0) are distributed to X, Y and Z, respectively.
Then, X computes and records (c0, c1)=(a0+b0, a1+b1), Y computes and records (c1, c2)=(a1+b1, a2+b2), and Z computes and records (c2, c0)=(a2+b2, a0 b0).
(3) Secure Computation of c=a+α (α is a Known Constant)
X computes and records (c0, c1)=(a0+a, a1) and Z computes and records (c2, c0)=(a2, a0+a). Y performs no operation.
(4) Secure Computation of c=a·α
X computes and records (c0, c1)=(a0·α, a1·α), Y computes and records (c1, c2)=(a1·α, a2·α), and Z computes and records (c2, c0)=(a2·α, a0·α).
(5) Secure Computation of c=a·b (Multiplication without Tampering Detection)
First, X generates random numbers r1, r2 and c0, computes c1=(a0+a1)(b0+b1)−r1−r2−c0 and sends (r1, c1) to Y and (r2, c0) to Z.
Then, Y computes y=a1·b2+b1·a2+r1 and sends y to Z. Z computes z=a2·b0+b2·a0+r2 and sends z to Y.
Then, Y and Z independently compute c2=y+z+a2·b2.
X records (c0, c1), Y records (c1, c2) and Z records (c2, c0).
(6) Secure Computation of c=a·b (Multiplication with Tampering Detection)
After the multiplication c=a·b according to the method in (5) described above, the following process is performed on each of X, Y and Z. Note that P in the process represents each of X, Y and Z; if P is X, P− represents Z and P+ represents Y; if P is Y, P− represents X and P+ represents Z, if P is Z, P− represents Y and P+ represents X.
First, P− and P+ alone generate and share a random number r and P− and P+ distribute r·a0, r·a1 and r·a2 to the parties as secret values for r·a. Then, c′=(r·α)·b is computed according to the method in (5) described above and determination is made as to whether r·c−c′ is equal to 0 or not. If r·c−c′ is not equal to 0, it is detected as tampering.
Secure function computation based on Shamir secret sharing in Non-patent literature 2 (hereinafter referred to as “Shamir's scheme”) is secure function computation without multiplication with tampering detection.